// 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
// 注意 这个数列必须是 严格 递增的。
/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumberOfLIS = function (nums) {
  const len = nums.length
  if (len === 0) {
    return 0
  }

  // dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度
  const dp = new Array(len).fill(0)
  // cnt[i] 表示以 nums[i] 结尾的最长上升子序列的个数
  const cnt = new Array(len).fill(0)

  let maxLen = 0
  let res = 0
  for (let i = 0; i < len; i++) {
    dp[i] = 1
    cnt[i] = 1
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        if (dp[j] + 1 > dp[i]) {
          dp[i] = dp[j] + 1
          cnt[i] = cnt[j]
        } else if (dp[j] + 1 === dp[i]) {
          cnt[i] += cnt[j]
        }
      }
    }
    if (dp[i] > maxLen) {
      maxLen = dp[i]
      res = cnt[i]
    } else if (dp[i] === maxLen) {
      res += cnt[i]
    }
  }

  return res
}

console.log(
  findNumberOfLIS([2, 2, 2, 2, 2])
)